//
// Description: 264. 丑数 II
// Created by Loading on 2022/6/28.
//

#include <bits/stdc++.h>

using namespace std;

int nthUglyNumber(int n) {
    // dp[i] 表示第 i + 1 个丑数
    vector<int> dp(n);
    dp[0] = 1;

    // 指数2、3、5的指针
    int ptr1 = 0, ptr2 = 0, ptr3 = 0;
    for (int i = 1; i < n; ++i) {
        // 选择较小的丑数放置
        dp[i] = min(min(dp[ptr1] * 2, dp[ptr2] * 3), dp[ptr3] * 5);
        // 各指针后移
        if (dp[i] == dp[ptr1] * 2) {
            ++ptr1;
        }
        if (dp[i] == dp[ptr2] * 3) {
            ++ptr2;
        }
        if (dp[i] == dp[ptr3] * 5) {
            ++ptr3;
        }
    }

    return dp[n - 1];
}

int main() {
    int n = 1690;

    int res = nthUglyNumber(n);

    cout << res << endl;

    return 0;
}
